class Solution:
    @classmethod
    def add_num(cls):
        cls.ugly_list = []
        for i in range(32):
            for j in range(21):
                for h in range(14):
                    cls.ugly_list.append((2 ** i) * (3 ** j) * (5 ** h))
        cls.ugly_list.sort()

    def nthUglyNumber(self, n: int) -> int:
        try:
            return Solution.ugly_list[n - 1]
        except:
            Solution.add_num()
            return Solution.ugly_list[n - 1]


class Solution2:
    def nthUglyNumber(self, n: int) -> int:
        res = [1]
        idx2 = 0
        idx3 = 0
        idx5 = 0
        for i in range(n-1):
            res.append(min(res[idx2]*2,res[idx3]*3,res[idx5]*5))
            if res[-1] == res[idx2]*2:
                idx2 += 1
            if res[-1] == res[idx3]*3:
                idx3 += 1
            if res[-1] == res[idx5]*5:
                idx5 += 1
        return res[-1]


a = Solution()
print(a.nthUglyNumber(100))
print(a.nthUglyNumber(1690))
b = Solution2()
print(b.nthUglyNumber(100))
print(b.nthUglyNumber(1690))
